import java.text.DecimalFormat;
import java.util.Iterator;
import java.util.TreeSet;

// simple item with weight and value attributes
class Item implements Comparable<Item> {
	public int weight;
	public int value;

	// constructor
	public Item(int weight, int value) {
		this.weight = weight;
		this.value = value;
	}

	@Override
	public int compareTo(Item o) {
		return weight - o.weight;
	}
}

public class Knapsack {

	// max weight allowed in this knapsack
	public int maxWeight;

	// all available items
	public Item[] items;

	// maximum value achieved by the solution
	public int maxValue;

	// used items for the solution
	// implemented as a TreeSet to get an ordered output
	public TreeSet<Item> usedItems = new TreeSet<Item>();

	public static void main(String[] args) {

		// Create knapsack with maxWeigth and add items
		Knapsack knapsack = new Knapsack(49);
		knapsack.items = new Item[] { new Item(1, 1), new Item(20, 21), new Item(2, 1), new Item(3, 3),
				new Item(4, 7), new Item(5, 3), new Item(6, 8), new Item(7, 7), new Item(8, 7),
				new Item(9, 9), new Item(10, 5), new Item(15, 20),
				new Item(25, 15) };

		knapsack.solveProblem();

		// print contents of the knapsack and the total value
		System.out.println("calculated maximum value: " + knapsack.maxValue);
		int totalValue = 0;
		int totalWeight = 0;
		for (Item item : knapsack.usedItems) {
			System.out.println("(" + item.weight + "," + item.value + ")");
			totalValue += item.value;
			totalWeight += item.weight;
		}
		System.out.println("knapsack value: " + totalValue + " (should be " + knapsack.maxValue
				+ ")");
		System.out.println("knapsack weight: " + totalWeight + " of " + knapsack.maxWeight);
	}

	// constructor
	Knapsack(int maxWeight) {
		this.maxWeight = maxWeight;
	}

	/*
	 * Implement a solution of task 7.1 here.
	 * 
	 * Use the variables "maxWeight" and "items" to get all needed information.
	 * 
	 * Store the calculated maximum value in the field "maxValue" and add all
	 * items which are used in the solution to the set "usedItems".
	 */
	private void solveProblem() {

		// memoizationField um rekursiv auf die schon errechneten Werte zuzugreifen
		int[][] memoizationField = new int[items.length][maxWeight + 1];
		
		
		//Initialisierung trivial
		for(int w = 0; w < maxWeight;w++)
			memoizationField[0][w] = 0;
		
		// In diesem Feld wird an der Stelle, an der das aktuelle Element in der optimalen Teillösung enthalten ist makiert.
		// Dies hilft später beim Finden der Element die die optimale Lösung des gesamtProblems darstellen.
		int[][] used = new int[items.length][maxWeight + 1];
			
		
		for(int currentItem = 0; currentItem < items.length; currentItem++)
			for(int currentWeight = 1; currentWeight <= maxWeight; currentWeight++)
			{
				// Dies muss gesondert behandelt werden, da es vor dem ersten Element keines gibt.
				if (currentItem == 0)
				{
					if((items[currentItem].weight <= currentWeight) 
							&& (items[currentItem].value > 0)) //dann ist das item teil der teilloesung
						{	
							memoizationField[currentItem][currentWeight] = items[currentItem].value;
							used[currentItem][currentWeight] = 1;
						}
						else
						{
							memoizationField[currentItem][currentWeight] = 0;
							used[currentItem][currentWeight] = 0;
						}
					
					continue;
				}
				
				// Muss nur betrachtet werden wenn das Gewicht größer gleich des Items ist, da das Item sonst gar nicht mitgenommen werden kann
				if((items[currentItem].weight <= currentWeight) 
						// Der value des aktuellen Items + dem des vorhergehenden. Dieses darf allerdings nur an der Stelle betrachtet werden an der es das Gewichtmax nicht übersteigt.
					&& (items[currentItem].value + memoizationField[currentItem -1][currentWeight - items[currentItem].weight] > memoizationField[currentItem-1][currentWeight])) //dann ist das item teil der teilloesung
				{	
					memoizationField[currentItem][currentWeight] = items[currentItem].value + memoizationField[currentItem-1][currentWeight - items[currentItem].weight];
					used[currentItem][currentWeight] = 1;
				}
				else
				{
					memoizationField[currentItem][currentWeight] = memoizationField[currentItem - 1][currentWeight];
					used[currentItem][currentWeight] = 0;
				}
			}
			

			maxValue = memoizationField[items.length - 1][maxWeight];
			
			// Hier werden die Elemente gesucht. 
			int k = maxWeight;
			for (int i = this.items.length - 1; i >= 0; i--) 
			{
				// Wenn das Element mit maxWeight einen Wert > 0 hat ist es Teil der Lösung.
				if (used[i][k] == 0) continue; 
				this.usedItems.add(this.items[i]);
				// Da das aktuelle Element nun schon im Rucksack ist muss dessen Gewicht abgezogen werden.
				k -= this.items[i].weight;
			}		
	}
}
